{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Hello LeetCode!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #string #dynamic-programming #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #字符串 #动态规划 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: Leetcode"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #Hello LeetCode!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "力扣嘉年华同样准备了纪念品展位，参观者只需要集齐 `helloleetcode` 的 `13` 张字母卡片即可获得力扣纪念章。\n",
    "\n",
    "在展位上有一些由字母卡片拼成的单词，`words[i][j]` 表示第 `i` 个单词的第 `j` 个字母。\n",
    "\n",
    "你可以从这些单词中取出一些卡片，但每次拿取卡片都需要消耗游戏代币，规则如下：\n",
    "\n",
    "- 从一个单词中取一个字母所需要的代币数量，为该字母左边和右边字母数量之积\n",
    "\n",
    "- 可以从一个单词中多次取字母，每个字母仅可被取一次\n",
    "\n",
    "> 例如：从 `example` 中取出字母 `a`，需要消耗代币 `2*4=8`，字母取出后单词变为 `exmple`；\n",
    "再从中取出字母 `m`，需要消耗代币 `2*3=6`，字母取出后单词变为 `exple`；\n",
    "\n",
    "请返回取得 `helloleetcode` 这些字母需要消耗代币的 **最少** 数量。如果无法取得，返回 `-1`。\n",
    "\n",
    "**注意：**\n",
    "- 取出字母的顺序没有要求\n",
    "- 取出的所有字母恰好可以拼成 `helloleetcode` \n",
    "\n",
    "**示例 1：**\n",
    ">输入：`words = [\"hold\",\"engineer\",\"cost\",\"level\"]`\n",
    ">\n",
    ">输出：`5`\n",
    ">\n",
    ">解释：最优方法为：\n",
    ">从 `hold` 依次取出 `h`、`o`、`l`、`d`， 代价均为 `0`\n",
    ">从 `engineer` 依次取出第 `1` 个 `e` 与最后一个 `e`， 代价为 `0` 和 `5*1=5`\n",
    ">从 `cost` 取出 `c`、`o`、`t`， 代价均为 `0`\n",
    ">从 `level` 依次取出 `l`、`l`、`e`、`e`， 代价均为 `0`\n",
    ">所有字母恰好可以拼成 `helloleetcode`，因此最小的代价为 `5`\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`words = [\"hello\",\"leetcode\"]`\n",
    ">\n",
    ">输出：`0`\n",
    "\n",
    "**提示：**\n",
    "+ `n == words.length`\n",
    "+ `m == words[i].length`\n",
    "+ `1 <= n <= 24`\n",
    "+ `1 <= m <= 8`\n",
    "+ `words[i][j]` 仅为小写字母"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [rMeRt2](https://leetcode.cn/problems/rMeRt2/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [rMeRt2](https://leetcode.cn/problems/rMeRt2/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"hold\",\"engineer\",\"cost\",\"level\"]', '[\"hello\",\"leetcode\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Manacher:\n",
    "    def __init__(self, string=''):\n",
    "        self.string = string\n",
    "\n",
    "    def add_char(self):\n",
    "        \"\"\"\n",
    "        对字符串预处理填充'#'，使得字符串长度强行满足奇数对称。\n",
    "        同时头尾插入一对不匹配字符，添加P数组计算的边界情况。\n",
    "        \"\"\"\n",
    "        add_string = '^'\n",
    "        for char in self.string:\n",
    "            add_string += '@' + char\n",
    "        add_string += '@*'\n",
    "        return add_string\n",
    "    \n",
    "    def get_p(self): # Manacher算法核心，利用对称性中心扩展O(n)计算P数组\n",
    "        self.add_string = self.add_char()\n",
    "        self.P = [0] * len(self.add_string)\n",
    "        R, mid = 0, 0\n",
    "        for i in range(1, len(self.add_string)-1):\n",
    "            self.P[i] = min(self.P[mid*2-i], R-i) if R > i else 0\n",
    "            while self.add_string[i+1+self.P[i]] == self.add_string[i-1-self.P[i]]:\n",
    "                self.P[i] +=1\n",
    "            if i + self.P[i] > R:\n",
    "                R = i + self.P[i]\n",
    "                mid = i    \n",
    "        return self.P\n",
    "    \n",
    "    def max_palindrome(self):\n",
    "        \"\"\"\n",
    "        利用manacher已计算好的P数组，输出最长的回文子串。可以直接解决 Leetcode 5. 最长回文子串\n",
    "        \"\"\"\n",
    "        self.get_p()\n",
    "        max_len, max_index = 0, 0\n",
    "        for index, value in enumerate(self.P):\n",
    "            if value > max_len:\n",
    "                max_len, max_index = value, index\n",
    "        start_index = (max_index - max_len) // 2\n",
    "        return self.string[start_index: start_index+max_len]\n",
    "\n",
    "    def check_partition_s(self, l, r): # 判断在串S的区间[l,r]的子串是否为回文串。\n",
    "        l, r = l * 2 + 2, r * 2 + 2\n",
    "        mid = (l + r) // 2\n",
    "        return self.P[mid] > r - mid\n",
    "        \n",
    "    def check_partition_p(self, l, r): # 判断在数组P的区间[l,r]内是否为回文串。\n",
    "        mid = (l + r) // 2\n",
    "        return self.P[mid] > r - mid\n",
    "\n",
    "class Solution:\n",
    "    def checkPartitioning(self, s: str) -> bool:\n",
    "        manacher = Manacher(s)\n",
    "        manacher.get_p()\n",
    "        n = len(s)\n",
    "        pre, suf = [], []\n",
    "        pre_vis, suf_vis = [0] * n, [0] * n\n",
    "        for i in range(0, n):\n",
    "            if manacher.check_partition_s(0, n-1-i):\n",
    "                pre.append(n-i-1)\n",
    "                pre_vis[n-i-1] = 1\n",
    "            if manacher.check_partition_s(i, n-1):\n",
    "                suf.append(i)\n",
    "                suf_vis[i] = 1\n",
    "\n",
    "        suf_n, cnt = len(suf), 0\n",
    "        for i in range(n):\n",
    "            if pre_vis[i]:\n",
    "                while cnt < suf_n and suf[cnt] < i + 2:\n",
    "                    cnt +=1\n",
    "                if cnt < suf_n and manacher.check_partition_s(i+1, suf[cnt]-1):\n",
    "                    return True\n",
    "        pre_n, cnt = len(pre), 0\n",
    "        for i in range(n-1, 0, -1):\n",
    "            if suf_vis[i]:\n",
    "                while cnt < pre_n and pre[cnt] + 2 > i:\n",
    "                    cnt +=1\n",
    "                if cnt < pre_n and manacher.check_partition_s(pre[cnt]+1, i-1):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef Leetcode(self, words):\n",
    "\t\tself.mark = {'c': 15625, 'd': 3125, 'h': 625, 't': 125, 'o': 25, 'l': 5, 'e': 1}\n",
    "\t\tlast = {19569: 0}\n",
    "\t\tfor w in words:\n",
    "\t\t\ttmp = self.calc(w)\n",
    "\t\t\tnxt = {}\n",
    "\t\t\tfor mark1 in last:\n",
    "\t\t\t\tfor mark2 in tmp:\n",
    "\t\t\t\t\tif self.chk(mark1, mark2):\n",
    "\t\t\t\t\t\tnxt[mark1 - mark2] = min(nxt.get(mark1 - mark2, float('inf')), last[mark1] + tmp[mark2])\n",
    "\t\t\tlast = nxt\n",
    "\t\treturn last.get(0, -1)\n",
    "\t\n",
    "\tdef calc(self, w):\n",
    "\t\tself.mark = {'c': 15625, 'd': 3125, 'h': 625, 't': 125, 'o': 25, 'l': 5, 'e': 1}\n",
    "\t\tres = {0: 0}\n",
    "\t\tpool = []\n",
    "\t\tfor i, char in enumerate(w):\n",
    "\t\t\tif char in self.mark:\n",
    "\t\t\t\tpool.append([i, self.mark[char]])\n",
    "\t\tk = len(pool)\n",
    "\t\tfor mark in range(1, 1 << k):\n",
    "\t\t\tself.update(len(w), [x for i, x in enumerate(pool) if mark >> i & 1 == 1], res)\n",
    "\t\treturn res\n",
    "\t\n",
    "\tdef update(self, n, stack, map0):\n",
    "\t\tcnt = {}\n",
    "\t\tmark = 0\n",
    "\t\tfor i, m in stack:\n",
    "\t\t\tcnt[m] = cnt.get(m, 0) + 1\n",
    "\t\t\tmark += m\n",
    "\t\tif max(cnt.values()) >= 5:\n",
    "\t\t\treturn\n",
    "\t\tl = 0\n",
    "\t\tr = len(stack) - 1\n",
    "\t\tlm = 0\n",
    "\t\trm = 0\n",
    "\t\tcost = 0\n",
    "\t\twhile l <= r:\n",
    "\t\t\tif stack[l][0] - lm <= n - 1 - stack[r][0] - rm:\n",
    "\t\t\t\tcost += (stack[l][0] - lm) * (n - 1 - rm - stack[l][0])\n",
    "\t\t\t\tl += 1\n",
    "\t\t\t\tlm += 1\n",
    "\t\t\telse:\n",
    "\t\t\t\tcost += (n - 1 - stack[r][0] - rm) * (stack[r][0] - lm)\n",
    "\t\t\t\tr -= 1\n",
    "\t\t\t\trm += 1\n",
    "\t\tmap0[mark] = min(map0.get(mark, float('inf')), cost)\n",
    "\t\n",
    "\tdef chk(self, m1, m2):\n",
    "\t\tfor base in [5,25,125,625,3125,15625,78125]:\n",
    "\t\t\tif m1 % base < m2 % base:\n",
    "\t\t\t\treturn False\n",
    "\t\treturn True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def Leetcode(self, words: List[str]) -> int:\n",
    "        N = len(words)\n",
    "        # 记录每个word中包含helloleetcode中的数量\n",
    "        ls = [0] * N\n",
    "\n",
    "        C = Counter(\"helloleetcode\")\n",
    "        M = len(C)\n",
    "\n",
    "        # 需要字符的数量\n",
    "        lv = list(C.values())\n",
    "        # 需要字符对应的索引\n",
    "        di = {c: i for i, c in enumerate(C)}\n",
    "\n",
    "        # 计算ls\n",
    "        for i, w in enumerate(words):\n",
    "            l = [0] * M\n",
    "            ls[i] = l\n",
    "\n",
    "            for j, c in enumerate(C):\n",
    "                l[j] = w.count(c)\n",
    "\n",
    "        # 记录需要字符的总数量\n",
    "        he = [l.copy() for l in ls]\n",
    "        for i in range(N - 2, -1, -1):\n",
    "            for j in range(M):\n",
    "                he[i][j] += he[i + 1][j]\n",
    "\n",
    "        # 判断总数量是否满足要求\n",
    "        for h, n in zip(he[0], lv):\n",
    "            if h < n:\n",
    "                return -1\n",
    "\n",
    "        # 记录已经计算的结果，增加递归效率\n",
    "        dp_one = {}\n",
    "\n",
    "        # w  —— 字符串\n",
    "        # lh —— 字符串中需要字符数量，保证和w一致\n",
    "        # ln —— 当前需要的数量\n",
    "        def calc_one(w, lh, ln):\n",
    "            # 使用w中i为，在需要字符中序号为ci\n",
    "            def use(i, ci):\n",
    "                ret = i * (N - i - 1)\n",
    "                lh[ci] -= 1\n",
    "                ln[ci] -= 1\n",
    "                _w = w[:i] + w[i + 1:]\n",
    "\n",
    "                ret += calc_one(_w, lh, ln)\n",
    "                dp_one[key] = ret\n",
    "                return ret\n",
    "\n",
    "            # 选择使用w中i为，在需要字符中序号为ci\n",
    "            def select(i, ci):\n",
    "                # 1. 使用\n",
    "                ret1 = i * (N - i - 1)\n",
    "\n",
    "                _lh = lh.copy()\n",
    "                _ln = ln.copy()\n",
    "                _lh[ci] -= 1\n",
    "                _ln[ci] -= 1\n",
    "                _w = w[:i] + w[i + 1:]\n",
    "\n",
    "                ret1 += calc_one(_w, _lh, _ln)\n",
    "\n",
    "                # 2. 不使用\n",
    "                # 修改为一个不可能的字符\n",
    "                _w = w[:i] + \"A\" + w[i + 1:]\n",
    "                lh[ci] -= 1\n",
    "                ret2 = calc_one(_w, lh, ln)\n",
    "\n",
    "                ret = min(ret1, ret2)\n",
    "                dp_one[key] = ret\n",
    "                return ret\n",
    "\n",
    "            allnum = sum(ln)\n",
    "            if allnum == 0:\n",
    "                return 0\n",
    "\n",
    "            key = str((w, ln))\n",
    "            ret = dp_one.get(key)\n",
    "            if ret != None:\n",
    "                return ret\n",
    "\n",
    "            N = len(w)\n",
    "\n",
    "            # 从首位开始看是否需要该字符\n",
    "            for i in range(N // 2):\n",
    "                qi = di.get(w[i])\n",
    "                if qi != None and ln[qi]:\n",
    "                    if lh[qi] == ln[qi] or allnum == 1:\n",
    "                        # i处必选\n",
    "                        return use(i, qi)\n",
    "\n",
    "                    qs = True\n",
    "                else:\n",
    "                    qs = False\n",
    "\n",
    "                hi = di.get(w[N - 1 - i])\n",
    "                if hi != None and ln[hi]:\n",
    "                    if lh[hi] == ln[hi] or allnum == 1:\n",
    "                        # N - 1 - i处必选\n",
    "                        return use(N - 1 - i, hi)\n",
    "\n",
    "                    hs = True\n",
    "                else:\n",
    "                    hs = False\n",
    "\n",
    "                if qs:\n",
    "                    return select(i, qi)\n",
    "\n",
    "                if hs:\n",
    "                    return select(N - 1 - i, hi)\n",
    "\n",
    "            # 奇数，并且刚好使用中间\n",
    "            ret = (N // 2) ** 2\n",
    "            dp_one[key] = ret\n",
    "            return ret\n",
    "\n",
    "        # 记录已经计算的结果，增加递归效率\n",
    "        dp = {}\n",
    "        MAX = len(\"helloleetcode\") * 16\n",
    "\n",
    "        def calc(i, l):\n",
    "            if i == N - 1:\n",
    "                return calc_one(words[-1], ls[-1][:], l)\n",
    "\n",
    "            key = str((i, l))\n",
    "            ret = dp.get(key)\n",
    "            if ret != None:\n",
    "                return ret\n",
    "\n",
    "            # 中当前lh_n取需要的字符，遍历每种取值的可能\n",
    "            def get(l, lh_n, lh_h, i=0):\n",
    "                v = []\n",
    "                while i < M:\n",
    "                    if l[i] == 0 or lh_h[i] == 0:\n",
    "                        # 不需要，或者后面没有了\n",
    "                        v.append(l[i])\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        break\n",
    "\n",
    "                if i == M:\n",
    "                    yield v\n",
    "                    return\n",
    "\n",
    "                maxnum = min(l[i], lh_n[i])\n",
    "                minnum = max(l[i] - lh_h[i], 0)\n",
    "\n",
    "                for num in range(minnum, maxnum + 1):\n",
    "                    _v = v + [num]\n",
    "                    for one in get(l, lh_n, lh_h, i + 1):\n",
    "                        yield _v + one\n",
    "\n",
    "            ret = MAX\n",
    "            for ln in get(l, ls[i], he[i + 1]):\n",
    "                _l = [e1 - e2 for e1, e2 in zip(l, ln)]\n",
    "                ret = min(ret, calc_one(words[i], ls[i][:], ln) + calc(i + 1, _l))\n",
    "\n",
    "            dp[key] = ret\n",
    "            return ret\n",
    "\n",
    "        ret = calc(0, lv)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "RULES = {\n",
    "    'e': (0, 4, 7),\n",
    "    'l': (3, 3, 3),\n",
    "    'o': (5, 2, 3),\n",
    "    'h': (7, 1, 1),\n",
    "    't': (8, 1, 1),\n",
    "    'c': (9, 1, 1),\n",
    "    'd': (10, 1, 1),\n",
    "}\n",
    "\n",
    "FULL = 2012\n",
    "def merge(cur: int, add: int) -> int:\n",
    "    for pos, limit, m in RULES.values():\n",
    "        c1 = (cur >> pos) & m\n",
    "        c2 = (add >> pos) & m\n",
    "        if c1 + c2 > limit: return -1\n",
    "        cur += c2 << pos\n",
    "    return cur\n",
    "\n",
    "class Solution:\n",
    "    def Leetcode(self, words: List[str]) -> int:\n",
    "        costs = []\n",
    "        for word in words:\n",
    "            cost = {}\n",
    "            def dfs(s: str, mask: int, tot: int) -> None:\n",
    "                if mask not in cost or tot < cost[mask]:\n",
    "                    cost[mask] = tot\n",
    "                for i, c in enumerate(s):\n",
    "                    if c not in RULES: continue\n",
    "                    pos, limit, m = RULES[c]\n",
    "                    if (mask >> pos) & m < limit:\n",
    "                        dfs(s[:i] + s[i + 1:], mask + (1 << pos), tot + i * (len(s) - 1 - i))\n",
    "            dfs(word, 0, 0)\n",
    "            costs.append(cost)\n",
    "        @cache\n",
    "        def dfs(i: int, mask: int) -> int:\n",
    "            if i == len(words):\n",
    "                return 0 if mask == FULL else inf\n",
    "            res = inf\n",
    "            for add, tot in costs[i].items():\n",
    "                if tot >= res: continue\n",
    "                m = merge(mask, add)\n",
    "                if m >= 0:\n",
    "                    res = min(res, tot + dfs(i + 1, m))\n",
    "            return res\n",
    "        ans = dfs(0, 0)\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "预处理 + 状态压缩dp\n",
    "1. 用位运算表示字母选择情况，由于一个字母可以选多个，\n",
    "因此要对二进制「分区」，每个区域表示对应字母的个数。\n",
    "2. 写一个记忆化搜索，f(i,mask) 表示从第 i 个单词开始选，已经选择的单词为 mask 时，\n",
    "后续消耗代币的最小值。枚举 words[i] 的所有合法选择方案转移到 f(i+1,mask′)。\n",
    "3. 因此需要预处理每个 words[i] 的每种选择字母的方案所消耗的代币的最小值，\n",
    "由于字符串很短，直接写个爆搜即可。\n",
    "'''\n",
    "# (字母在二进制上的起始位置, 这个字母能选择的上限, 位掩码)\n",
    "RULES = {\n",
    "    'e': (0, 4, 7),\n",
    "    'l': (3, 3, 3),\n",
    "    'o': (5, 2, 3),\n",
    "    'h': (7, 1, 1),\n",
    "    't': (8, 1, 1),\n",
    "    'c': (9, 1, 1),\n",
    "    'd': (10, 1, 1),\n",
    "}\n",
    "FULL = 2012  # 0b11111011100，每个字母都选到了对应的上限\n",
    "\n",
    "# 合并两种选择字母的方案\n",
    "def merge(cur: int, add: int) -> int:\n",
    "    for pos, limit, m in RULES.values():\n",
    "        c1 = (cur >> pos) & m\n",
    "        c2 = (add >> pos) & m\n",
    "        if c1 + c2 > limit: return -1\n",
    "        cur += c2 << pos\n",
    "    return cur\n",
    "\n",
    "class Solution:\n",
    "    def Leetcode(self, words: List[str]) -> int:\n",
    "        # 预处理每个单词的每种选择字母的方案所消耗的代币的最小值\n",
    "        costs = []\n",
    "        for word in words:\n",
    "            cost = {}\n",
    "            def dfs(s: str, mask: int, tot: int) -> None:\n",
    "                if mask not in cost or tot < cost[mask]:\n",
    "                    cost[mask] = tot\n",
    "                for i, c in enumerate(s):  # 枚举选择字母的位置\n",
    "                    if c not in RULES: continue\n",
    "                    pos, limit, m = RULES[c]\n",
    "                    if (mask >> pos) & m < limit:  # 可以选字母 c\n",
    "                        dfs(s[:i] + s[i + 1:], mask + (1 << pos), tot + i * (len(s) - 1 - i))\n",
    "            dfs(word, 0, 0)\n",
    "            costs.append(cost)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, mask: int) -> int:\n",
    "            if i == len(words):\n",
    "                return 0 if mask == FULL else inf  # inf 表示不合法，没有选完要求的字母\n",
    "            res = inf\n",
    "            for add, tot in costs[i].items():\n",
    "                if tot >= res: continue  # 剪枝\n",
    "                m = merge(mask, add)\n",
    "                if m >= 0:\n",
    "                    res = min(res, tot + dfs(i + 1, m))\n",
    "            return res\n",
    "        ans = dfs(0, 0)\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# (字母在二进制上的起始位置, 这个字母能选择的上限, 位掩码)\n",
    "RULES = {\n",
    "    'e': (0, 4, 7),\n",
    "    'l': (3, 3, 3),\n",
    "    'o': (5, 2, 3),\n",
    "    'h': (7, 1, 1),\n",
    "    't': (8, 1, 1),\n",
    "    'c': (9, 1, 1),\n",
    "    'd': (10, 1, 1),\n",
    "}\n",
    "FULL = 2012  # 0b11111011100，每个字母都选到了对应的上限\n",
    "\n",
    "# 合并两种选择字母的方案\n",
    "def merge(cur: int, add: int) -> int:\n",
    "    for pos, limit, m in RULES.values():\n",
    "        c1 = (cur >> pos) & m\n",
    "        c2 = (add >> pos) & m\n",
    "        if c1 + c2 > limit: return -1\n",
    "        cur += c2 << pos\n",
    "    return cur\n",
    "\n",
    "class Solution:\n",
    "    def Leetcode(self, words: List[str]) -> int:\n",
    "        # 预处理每个单词的每种选择字母的方案所消耗的代币的最小值\n",
    "        costs = []\n",
    "        for word in words:\n",
    "            cost = {}\n",
    "            def dfs(s: str, mask: int, tot: int) -> None:\n",
    "                if mask not in cost or tot < cost[mask]:\n",
    "                    cost[mask] = tot\n",
    "                for i, c in enumerate(s):  # 枚举选择字母的位置\n",
    "                    if c not in RULES: continue\n",
    "                    pos, limit, m = RULES[c]\n",
    "                    if (mask >> pos) & m < limit:  # 可以选字母 c\n",
    "                        dfs(s[:i] + s[i + 1:], mask + (1 << pos), tot + i * (len(s) - 1 - i))\n",
    "            dfs(word, 0, 0)\n",
    "            costs.append(cost)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, mask: int) -> int:\n",
    "            if i == len(words):\n",
    "                return 0 if mask == FULL else inf  # inf 表示不合法，没有选完要求的字母\n",
    "            res = inf\n",
    "            for add, tot in costs[i].items():\n",
    "                if tot >= res: continue  # 剪枝\n",
    "                m = merge(mask, add)\n",
    "                if m >= 0:\n",
    "                    res = min(res, tot + dfs(i + 1, m))\n",
    "            return res\n",
    "        ans = dfs(0, 0)\n",
    "        return ans if ans < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# (字母在二进制上的起始位置, 这个字母能选择的上限, 位掩码)\n",
    "RULES = {\n",
    "    'e': (0, 4, 7),\n",
    "    'l': (3, 3, 3),\n",
    "    'o': (5, 2, 3),\n",
    "    'h': (7, 1, 1),\n",
    "    't': (8, 1, 1),\n",
    "    'c': (9, 1, 1),\n",
    "    'd': (10, 1, 1),\n",
    "}\n",
    "FULL = 2012  # 0b11111011100，每个字母都选到了对应的上限\n",
    "\n",
    "# 合并两种选择字母的方案\n",
    "def merge(cur: int, add: int) -> int:\n",
    "    for pos, limit, m in RULES.values():\n",
    "        c1 = (cur >> pos) & m\n",
    "        c2 = (add >> pos) & m\n",
    "        if c1 + c2 > limit: return -1\n",
    "        cur += c2 << pos\n",
    "    return cur\n",
    "\n",
    "class Solution:\n",
    "    def Leetcode(self, words: List[str]) -> int:\n",
    "        # 预处理每个单词的每种选择字母的方案所消耗的代币的最小值\n",
    "        costs = []\n",
    "        for word in words:\n",
    "            cost = {}\n",
    "            def dfs(s: str, mask: int, tot: int) -> None:\n",
    "                if mask not in cost or tot < cost[mask]:\n",
    "                    cost[mask] = tot\n",
    "                for i, c in enumerate(s):  # 枚举选择字母的位置\n",
    "                    if c not in RULES: continue\n",
    "                    pos, limit, m = RULES[c]\n",
    "                    if (mask >> pos) & m < limit:  # 可以选字母 c\n",
    "                        dfs(s[:i] + s[i + 1:], mask + (1 << pos), tot + i * (len(s) - 1 - i))\n",
    "            dfs(word, 0, 0)\n",
    "            costs.append(cost)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, mask: int) -> int:\n",
    "            if i == len(words):\n",
    "                return 0 if mask == FULL else inf  # inf 表示不合法，没有选完要求的字母\n",
    "            res = inf\n",
    "            for add, tot in costs[i].items():\n",
    "                if tot >= res: continue  # 剪枝\n",
    "                m = merge(mask, add)\n",
    "                if m >= 0:\n",
    "                    res = min(res, tot + dfs(i + 1, m))\n",
    "            return res\n",
    "        ans = dfs(0, 0)\n",
    "        return ans if ans < inf else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "多重集合\n",
    "'''\n",
    "RULES={\n",
    "    'e':(0,4,7),\n",
    "    'l':(3,3,3),\n",
    "    'o':(5,2,3),\n",
    "    'h':(7,1,1),\n",
    "    't':(8,1,1),\n",
    "    'c':(9,1,1),\n",
    "    'd':(10,1,1)\n",
    "}\n",
    "FULL=2012\n",
    "\n",
    "class Solution:\n",
    "    def Leetcode(self, words: List[str]) -> int:\n",
    "        #枚举每个word能组成的有效集合，以及对应的代价\n",
    "        #f[i][j]代表前i个word组成集合j的最小代价\n",
    "        #f[i][j]=if merge(j^s,s) f[i-1][j^s]+cnt[i][s] 我们需要枚举每个cnt[i]中的有效集合s\n",
    "        counts=[]\n",
    "        for word in words:\n",
    "            cnt={}\n",
    "            def dfs(s:str,mask:int,score:int)->None:\n",
    "                if mask not in cnt or score<cnt[mask]:\n",
    "                    cnt[mask]=score\n",
    "                for i,c in enumerate(s):\n",
    "                    #选择字符s\n",
    "                    if c not in RULES:continue\n",
    "                    pos,limit,m=RULES[c]\n",
    "                    if (mask>>pos)&m<limit:\n",
    "                        dfs(s[:i]+s[i+1:],mask+(1<<pos),score+i*(len(s)-i-1))\n",
    "            dfs(word,0,0)\n",
    "            counts.append(cnt)\n",
    "        def merge(mask:int,add:int)->int:\n",
    "            #不会就暴力\n",
    "            ans=0\n",
    "            for pos,limit,m in RULES.values():\n",
    "                cnt1=(mask>>pos)&m    \n",
    "                cnt2=(add>>pos)&m    \n",
    "                if (cnt1+cnt2)<=limit:\n",
    "                    ans+=(cnt1+cnt2)<<pos   \n",
    "                else:\n",
    "                    return -1\n",
    "            return ans\n",
    "        #暴力枚举每个位置的可能即可\n",
    "        @cache\n",
    "        def dfs(i:int,mask:int)->int:\n",
    "            ans=inf\n",
    "            if i==len(words):\n",
    "                return ans if mask!=FULL else 0\n",
    "            for add,s in counts[i].items():\n",
    "                if s >= ans: continue  # 剪枝\n",
    "                if merge(mask,add)>=0:\n",
    "                    ans=min(ans,s+dfs(i+1,merge(mask,add)))\n",
    "            return ans\n",
    "        ans=dfs(0,0)\n",
    "        return ans if ans<inf else -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "多重集合\n",
    "'''\n",
    "RULES={\n",
    "    'e':(0,4,7),\n",
    "    'l':(3,3,3),\n",
    "    'o':(5,2,3),\n",
    "    'h':(7,1,1),\n",
    "    't':(8,1,1),\n",
    "    'c':(9,1,1),\n",
    "    'd':(10,1,1)\n",
    "}\n",
    "FULL=2012\n",
    "\n",
    "class Solution:\n",
    "    def Leetcode(self, words: List[str]) -> int:\n",
    "        #枚举每个word能组成的有效集合，以及对应的代价\n",
    "        #f[i][j]代表前i个word组成集合j的最小代价\n",
    "        #f[i][j]=if merge(j^s,s) f[i-1][j^s]+cnt[i][s] 我们需要枚举每个cnt[i]中的有效集合s\n",
    "        counts=[]\n",
    "        for word in words:\n",
    "            cnt={}\n",
    "            def dfs(s:str,mask:int,score:int)->None:\n",
    "                if mask not in cnt or score<cnt[mask]:\n",
    "                    cnt[mask]=score\n",
    "                for i,c in enumerate(s):\n",
    "                    #选择字符s\n",
    "                    if c not in RULES:continue\n",
    "                    pos,limit,m=RULES[c]\n",
    "                    if (mask>>pos)&m<limit:\n",
    "                        dfs(s[:i]+s[i+1:],mask+(1<<pos),score+i*(len(s)-i-1))\n",
    "            dfs(word,0,0)\n",
    "            counts.append(cnt)\n",
    "        def merge(cur: int, add: int) -> int:\n",
    "            for pos, limit, m in RULES.values():\n",
    "                c1 = (cur >> pos) & m\n",
    "                c2 = (add >> pos) & m\n",
    "                if c1 + c2 > limit: return -1\n",
    "                cur += c2 << pos\n",
    "            return cur\n",
    "\n",
    "\n",
    "        #暴力枚举每个位置的可能即可\n",
    "        @cache\n",
    "        def dfs(i: int, mask: int) -> int:\n",
    "            if i == len(words):\n",
    "                return 0 if mask == FULL else inf  # inf 表示不合法，没有选完要求的字母\n",
    "            res = inf\n",
    "            for add, tot in counts[i].items():\n",
    "                if tot >= res: continue  # 剪枝\n",
    "                m = merge(mask, add)\n",
    "                if m >= 0:\n",
    "                    res = min(res, tot + dfs(i + 1, m))\n",
    "            return res\n",
    "        ans = dfs(0, 0)\n",
    "        return ans if ans < inf else -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "多重集合\n",
    "'''\n",
    "RULES={\n",
    "    'e':(0,4,7),\n",
    "    'l':(3,3,3),\n",
    "    'o':(5,2,3),\n",
    "    'h':(7,1,1),\n",
    "    't':(8,1,1),\n",
    "    'c':(9,1,1),\n",
    "    'd':(10,1,1)\n",
    "}\n",
    "FULL=2012\n",
    "\n",
    "class Solution:\n",
    "    def Leetcode(self, words: List[str]) -> int:\n",
    "        #枚举每个word能组成的有效集合，以及对应的代价\n",
    "        #f[i][j]代表前i个word组成集合j的最小代价\n",
    "        #f[i][j]=if merge(j^s,s) f[i-1][j^s]+cnt[i][s] 我们需要枚举每个cnt[i]中的有效集合s\n",
    "        counts=[]\n",
    "        for word in words:\n",
    "            cnt={}\n",
    "            def dfs(s:str,mask:int,score:int)->None:\n",
    "                if mask not in cnt or score<cnt[mask]:\n",
    "                    cnt[mask]=score\n",
    "                for i,c in enumerate(s):\n",
    "                    #选择字符s\n",
    "                    if c not in RULES:continue\n",
    "                    pos,limit,m=RULES[c]\n",
    "                    if (mask>>pos)&m<limit:\n",
    "                        dfs(s[:i]+s[i+1:],mask+(1<<pos),score+i*(len(s)-i-1))\n",
    "            dfs(word,0,0)\n",
    "            counts.append(cnt)\n",
    "        def merge(cur: int, add: int) -> int:\n",
    "            for pos, limit, m in RULES.values():\n",
    "                c1 = (cur >> pos) & m\n",
    "                c2 = (add >> pos) & m\n",
    "                if c1 + c2 > limit: return -1\n",
    "                cur += c2 << pos\n",
    "            return cur\n",
    "\n",
    "\n",
    "        #暴力枚举每个位置的可能即可\n",
    "        @cache\n",
    "        def dfs(i:int,mask:int)->int:\n",
    "            ans=inf\n",
    "            if i==len(words):\n",
    "                return ans if mask!=FULL else 0\n",
    "            for add,s in counts[i].items():\n",
    "                if s >= ans: continue  # 剪枝\n",
    "                m=merge(mask, add)\n",
    "                if m>=0:\n",
    "                    ans=min(ans,s+dfs(i+1,m))\n",
    "            return ans\n",
    "        ans=dfs(0,0)\n",
    "        return ans if ans<inf else -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "RULES = {\n",
    "    'e': (0, 4, 7),\n",
    "    'l': (3, 3, 3),\n",
    "    'o': (5, 2, 3),\n",
    "    'h': (7, 1, 1),\n",
    "    't': (8, 1, 1),\n",
    "    'c': (9, 1, 1),\n",
    "    'd': (10, 1, 1),\n",
    "}\n",
    "FULL = 2012  # 0b11111011100，每个字母都选到了对应的上限\n",
    "\n",
    "class Solution:\n",
    "    def Leetcode(self, words: List[str]) -> int:\n",
    "        costs = []\n",
    "        for word in words:\n",
    "            cost = {}\n",
    "            def dfs(s: str, mask: int, tot: int) -> None:\n",
    "                if mask not in cost or tot < cost[mask]:\n",
    "                    cost[mask] = tot\n",
    "                for i, c in enumerate(s):  # 枚举选择字母的位置\n",
    "                    if c not in RULES: continue\n",
    "                    pos, limit, m = RULES[c]\n",
    "                    if (mask >> pos) & m < limit:  # 可以选字母 c\n",
    "                        dfs(s[:i] + s[i + 1:], mask + (1 << pos), tot + i * (len(s) - 1 - i))\n",
    "            dfs(word, 0, 0)\n",
    "            costs.append(cost)\n",
    "\n",
    "        def merge(cur: int, add: int) -> int:\n",
    "            for pos, limit, m in RULES.values():\n",
    "                c1 = (cur >> pos) & m\n",
    "                c2 = (add >> pos) & m\n",
    "                if c1 + c2 > limit: return -1\n",
    "                cur += c2 << pos\n",
    "            return cur\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, mask: int) -> int:\n",
    "            if i == len(words):\n",
    "                return 0 if mask == FULL else inf  # inf 表示不合法，没有选完要求的字母\n",
    "            res = inf\n",
    "            for add, tot in costs[i].items():\n",
    "                if tot >= res: continue  # 剪枝\n",
    "                m = merge(mask, add)\n",
    "                if m >= 0:\n",
    "                    res = min(res, tot + dfs(i + 1, m))\n",
    "            return res \n",
    "        ans=dfs(0,0)\n",
    "        return ans if ans<inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "多重集合\n",
    "'''\n",
    "RULES={\n",
    "    'e':(0,4,7),\n",
    "    'l':(3,3,3),\n",
    "    'o':(5,2,3),\n",
    "    'h':(7,1,1),\n",
    "    't':(8,1,1),\n",
    "    'c':(9,1,1),\n",
    "    'd':(10,1,1)\n",
    "}\n",
    "FULL=2012\n",
    "\n",
    "class Solution:\n",
    "    def Leetcode(self, words: List[str]) -> int:\n",
    "        #枚举每个word能组成的有效集合，以及对应的代价\n",
    "        #f[i][j]代表前i个word组成集合j的最小代价\n",
    "        #f[i][j]=if merge(j^s,s) f[i-1][j^s]+cnt[i][s] 我们需要枚举每个cnt[i]中的有效集合s\n",
    "        counts=[]\n",
    "        for word in words:\n",
    "            cnt={}\n",
    "            def dfs(s:str,mask:int,score:int)->None:\n",
    "                if mask not in cnt or score<cnt[mask]:\n",
    "                    cnt[mask]=score\n",
    "                for i,c in enumerate(s):\n",
    "                    #选择字符s\n",
    "                    if c not in RULES:continue\n",
    "                    pos,limit,m=RULES[c]\n",
    "                    if (mask>>pos)&m<limit:\n",
    "                        dfs(s[:i]+s[i+1:],mask+(1<<pos),score+i*(len(s)-i-1))\n",
    "            dfs(word,0,0)\n",
    "            counts.append(cnt)\n",
    "        def merge(cur: int, add: int) -> int:\n",
    "            for pos, limit, m in RULES.values():\n",
    "                c1 = (cur >> pos) & m\n",
    "                c2 = (add >> pos) & m\n",
    "                if c1 + c2 > limit: return -1\n",
    "                cur += c2 << pos\n",
    "            return cur\n",
    "\n",
    "\n",
    "        #暴力枚举每个位置的可能即可\n",
    "        @cache\n",
    "        def dfs(i:int,mask:int)->int:\n",
    "            ans=inf\n",
    "            if i==len(words):\n",
    "                return ans if mask!=FULL else 0\n",
    "            for add,s in counts[i].items():\n",
    "                if s >= ans: continue  # 剪枝\n",
    "                if merge(mask,add)>=0:\n",
    "                    ans=min(ans,s+dfs(i+1,merge(mask,add)))\n",
    "            return ans\n",
    "        ans=dfs(0,0)\n",
    "        return ans if ans<inf else -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "RULES = {'e': (0, 4, 7), 'l': (3, 3, 3), 'o': (5, 2, 3), 'h': (7, 1, 1), 't': (8, 1, 1), 'c': (9, 1, 1), 'd': (10, 1, 1)}\n",
    "FULL = 2012\n",
    "\n",
    "def merge(cur: int, add: int) -> int:\n",
    "    for pos, limit, m in RULES.values():\n",
    "        c1 = (cur >> pos) & m\n",
    "        c2 = (add >> pos) & m\n",
    "        if c1 + c2 > limit:\n",
    "            return -1\n",
    "        cur += c2 << pos\n",
    "    return cur\n",
    "\n",
    "class Solution:\n",
    "    def Leetcode(self, words: List[str]) -> int:\n",
    "        cost = []\n",
    "        for word in words:\n",
    "            cost_dict = {}\n",
    "            def dfs(s: str, mask: int, tot: int) -> None:\n",
    "                if mask not in cost_dict or tot < cost_dict[mask]:\n",
    "                    cost_dict[mask] = tot\n",
    "                for i, c in enumerate(s):\n",
    "                    if c not in RULES:\n",
    "                        continue\n",
    "                    pos, limit, m = RULES[c]\n",
    "                    if (mask >> pos) & m < limit:\n",
    "                        dfs(s[:i] + s[i+1:], mask + (1 << pos), tot + i * (len(s) - 1 - i))\n",
    "            dfs(word, 0, 0)\n",
    "            cost.append(cost_dict)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i: int, mask: int) -> int:\n",
    "            if i == len(words):\n",
    "                return 0 if mask == FULL else float('inf')\n",
    "            res = float('inf')\n",
    "            for add, tot in cost[i].items():\n",
    "                if tot >= res:\n",
    "                    continue\n",
    "                m = merge(mask, add)\n",
    "                if m >= 0:\n",
    "                    res = min(res, tot + dfs(i+1, m))\n",
    "            return res\n",
    "        \n",
    "        ans = dfs(0, 0)\n",
    "        return ans if ans < float('inf') else -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "RULES = {\n",
    "    'e': (0, 4, 7),\n",
    "    'l': (3, 3, 3),\n",
    "    'o': (5, 2, 3),\n",
    "    'h': (7, 1, 1),\n",
    "    't': (8, 1, 1),\n",
    "    'c': (9, 1, 1),\n",
    "    'd': (10, 1, 1),\n",
    "}\n",
    "FULL = 2012\n",
    "\n",
    "def merge(cur: int, add: int) -> int:\n",
    "    for pos, limit, m in RULES.values():\n",
    "        c1 = (cur >> pos) & m\n",
    "        c2 = (add >> pos) & m\n",
    "        if c1 + c2 > limit: return -1\n",
    "        cur += c2 << pos\n",
    "    return cur\n",
    "\n",
    "class Solution:\n",
    "    def Leetcode(self, words: List[str]) -> int:\n",
    "        costs = []\n",
    "        for word in words:\n",
    "            cost = {}\n",
    "            def dfs(s: str, mask: int, tot: int) -> None:\n",
    "                if mask not in cost or tot < cost[mask]:\n",
    "                    cost[mask] = tot\n",
    "                for i, c in enumerate(s):  \n",
    "                    if c not in RULES: continue\n",
    "                    pos, limit, m = RULES[c]\n",
    "                    if (mask >> pos) & m < limit:\n",
    "                        dfs(s[:i] + s[i + 1:], mask + (1 << pos), tot + i * (len(s) - 1 - i))\n",
    "            dfs(word, 0, 0)\n",
    "            costs.append(cost)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, mask: int) -> int:\n",
    "            if i == len(words):\n",
    "                return 0 if mask == FULL else float('inf')\n",
    "            res = float('inf')\n",
    "            for add, tot in costs[i].items():\n",
    "                if tot >= res: continue  \n",
    "                m = merge(mask, add)\n",
    "                if m >= 0:\n",
    "                    res = min(res, tot + dfs(i + 1, m))\n",
    "            return res\n",
    "        ans = dfs(0, 0)\n",
    "        return ans if ans < float('inf') else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# @author __snake__\n",
    "\n",
    "TARGET = 'helloleetcode'\n",
    "CNT = Counter(TARGET)\n",
    "# 十进制状态压缩\n",
    "MAP = {'e': 1, 'l': 10, 'o': 100, 'c': 1000, 'd': 10000, 'h': 100000, 't': 1000000}\n",
    "# INIT 表示需要的卡片字母的初始数量, (INIT // MAP[x] % 10)就是字母x需要的数量\n",
    "# 同样的,将字母x需要数量减去n: mask - n * MAP[x] (mask表示当前需要的卡片) \n",
    "INIT = 1111234\n",
    "class Solution:\n",
    "    def Leetcode(self, words: List[str]) -> int:\n",
    "        L = len(words)\n",
    "        # 枚举字符串s各种可用的组合和其对应花费, \n",
    "        # 比如'hold'可用的有'h': 0, 'hol': 0, 'oh': 2 ...\n",
    "        def getUsable(s):\n",
    "            ans, lis = defaultdict(lambda: inf), []\n",
    "            def traceback(s, cost):\n",
    "                res = ''.join(sorted(lis))\n",
    "                # 相同卡片组花费取花费较少的\n",
    "                ans[res] = min(cost, ans[res])\n",
    "                for i, x in enumerate(s):\n",
    "                    if x in MAP:\n",
    "                        lis.append(x)\n",
    "                        traceback(s[:i] + s[i + 1:], cost + i * (len(s) - i - 1))\n",
    "                        lis.pop()\n",
    "        \n",
    "            traceback(s, 0)\n",
    "            return ans\n",
    "        # 预处理出每个单词的可用卡片组\n",
    "        usables = [getUsable(w) for w in words]\n",
    "\n",
    "        @cache\n",
    "        def dfs(idx, mask):\n",
    "            if mask == 0: return 0\n",
    "            if idx == L: return inf\n",
    "            dic = usables[idx]\n",
    "            ans = inf\n",
    "            for s, cost in dic.items():\n",
    "                m = mask\n",
    "                for x in s:\n",
    "                    v = MAP[x]\n",
    "                    if m // v % 10 == 0: break\n",
    "                    m -= v\n",
    "                else:\n",
    "                    if (val := cost + dfs(idx + 1, m)) < ans: ans = val\n",
    "            return ans\n",
    "\n",
    "        ans = dfs(0, INIT)  \n",
    "        return ans if ans < inf else -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# @author __snake__\n",
    "# 十进制状态压缩\n",
    "MAP = {'e': 1, 'l': 10, 'o': 100, 'c': 1000, 'd': 10000, 'h': 100000, 't': 1000000}\n",
    "# INIT 表示需要的卡片字母的初始数量, (INIT // MAP[x] % 10)就是字母x需要的数量\n",
    "# 同样的,将字母x需要数量减去n: mask - n * MAP[x] (mask表示当前需要的卡片) \n",
    "INIT = 1111234\n",
    "class Solution:\n",
    "    def Leetcode(self, words: List[str]) -> int:\n",
    "        L = len(words)\n",
    "        # 枚举字符串s各种可用的组合和其对应花费, \n",
    "        # 比如'hold'可用的有'h': 0, 'hol': 0, 'oh': 2 ...\n",
    "        def getUsable(s):\n",
    "            ans, lis = defaultdict(lambda: inf), []\n",
    "            def traceback(s, cost):\n",
    "                res = ''.join(sorted(lis))\n",
    "                # 相同卡片组取花费较少的\n",
    "                ans[res] = min(cost, ans[res])\n",
    "                for i, x in enumerate(s):\n",
    "                    if x in MAP:\n",
    "                        lis.append(x)\n",
    "                        traceback(s[:i] + s[i + 1:], cost + i * (len(s) - i - 1))\n",
    "                        lis.pop()\n",
    "        \n",
    "            traceback(s, 0)\n",
    "            return ans\n",
    "        # 预处理出每个单词的可用卡片组\n",
    "        usables = [getUsable(w) for w in words]\n",
    "\n",
    "        @cache\n",
    "        def dfs(idx, mask):\n",
    "            if mask == 0: return 0\n",
    "            if idx == L: return inf\n",
    "            dic = usables[idx]\n",
    "            ans = inf\n",
    "            for s, cost in dic.items():\n",
    "                m = mask\n",
    "                for x in s:\n",
    "                    v = MAP[x]\n",
    "                    if m // v % 10 == 0: break\n",
    "                    m -= v\n",
    "                else:\n",
    "                    if (val := cost + dfs(idx + 1, m)) < ans: ans = val\n",
    "            return ans\n",
    "\n",
    "        ans = dfs(0, INIT)  \n",
    "        return ans if ans < inf else -1\n",
    "\n",
    "# 作者：白莉爱吃巧克力\n",
    "# 链接：https://leetcode.cn/problems/rMeRt2/solutions/2275322/python-hui-su-yu-chu-li-ji-yi-hua-sou-su-q8vp/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "RULES = {\n",
    "    'e': (0, 4, 7),\n",
    "    'l': (3, 3, 3),\n",
    "    'o': (5, 2, 3),\n",
    "    'h': (7, 1, 1),\n",
    "    't': (8, 1, 1),\n",
    "    'c': (9, 1, 1),\n",
    "    'd': (10, 1, 1),\n",
    "}\n",
    "FULL = 2012\n",
    "\n",
    "def merge(cur: int, add: int) -> int:\n",
    "    for pos, limit, m in RULES.values():\n",
    "        c1 = (cur >> pos) & m\n",
    "        c2 = (add >> pos) & m\n",
    "        if c1 + c2 > limit: return -1\n",
    "        cur += c2 << pos\n",
    "    return cur\n",
    " \n",
    "class Solution:\n",
    "    def Leetcode(self, words: List[str]) -> int:\n",
    "        costs = []\n",
    "        for word in words:\n",
    "            cost = {}\n",
    "            def dfs(s: str, mask: int, tot: int) -> None:\n",
    "                if mask not in cost or tot < cost[mask]:\n",
    "                    cost[mask] = tot\n",
    "                for i, c in enumerate(s):\n",
    "                    if c not in RULES: continue\n",
    "                    pos, limit, m = RULES[c]\n",
    "                    if (mask >> pos) & m < limit:\n",
    "                        dfs(s[:i] + s[i+1:], mask + (1 << pos), tot + i * (len(s) - i - 1))\n",
    "            dfs(word, 0, 0)\n",
    "            costs.append(cost)\n",
    "        @cache\n",
    "        def dfs(i: int, mask: int) -> int:\n",
    "            if i == len(words):\n",
    "                return inf if mask != FULL else 0\n",
    "            res = inf\n",
    "            for add, tot in costs[i].items():\n",
    "                m = merge(mask, add)\n",
    "                if m != -1:\n",
    "                    res = min(res, dfs(i + 1, m) + tot)\n",
    "            return res\n",
    "        ans = dfs(0, 0)\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "多重集合\n",
    "'''\n",
    "RULES={\n",
    "    'e':(0,4,7),\n",
    "    'l':(3,3,3),\n",
    "    'o':(5,2,3),\n",
    "    'h':(7,1,1),\n",
    "    't':(8,1,1),\n",
    "    'c':(9,1,1),\n",
    "    'd':(10,1,1)\n",
    "}\n",
    "FULL=2012\n",
    "\n",
    "class Solution:\n",
    "    def Leetcode(self, words: List[str]) -> int:\n",
    "        #枚举每个word能组成的有效集合，以及对应的代价\n",
    "        #f[i][j]代表前i个word组成集合j的最小代价\n",
    "        #f[i][j]=if merge(j^s,s) f[i-1][j^s]+cnt[i][s] 我们需要枚举每个cnt[i]中的有效集合s\n",
    "        counts=[]\n",
    "        for word in words:\n",
    "            cnt={}\n",
    "            def dfs(s:str,mask:int,score:int)->None:\n",
    "                if mask not in cnt or score<cnt[mask]:\n",
    "                    cnt[mask]=score\n",
    "                for i,c in enumerate(s):\n",
    "                    #选择字符s\n",
    "                    if c not in RULES:continue\n",
    "                    pos,limit,m=RULES[c]\n",
    "                    if (mask>>pos)&m<limit:\n",
    "                        dfs(s[:i]+s[i+1:],mask+(1<<pos),score+i*(len(s)-i-1))\n",
    "            dfs(word,0,0)\n",
    "            counts.append(cnt)\n",
    "        def merge(cur: int, add: int) -> int:\n",
    "            for pos, limit, m in RULES.values():\n",
    "                c1 = (cur >> pos) & m\n",
    "                c2 = (add >> pos) & m\n",
    "                if c1 + c2 > limit: return -1\n",
    "                cur += c2 << pos\n",
    "            return cur\n",
    "\n",
    "\n",
    "        #暴力枚举每个位置的可能即可\n",
    "        @cache\n",
    "        def dfs(i: int, mask: int) -> int:\n",
    "            if i == len(words):\n",
    "                return 0 if mask == FULL else inf  # inf 表示不合法，没有选完要求的字母\n",
    "            res = inf\n",
    "            for add, tot in counts[i].items():\n",
    "                # if tot >= res: continue  # 剪枝\n",
    "                m = merge(mask, add)\n",
    "                if m >= 0:\n",
    "                    res = min(res, tot + dfs(i + 1, m))\n",
    "            return res\n",
    "        ans = dfs(0, 0)\n",
    "        return ans if ans < inf else -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def Leetcode(self, words: List[str]) -> int:\n",
    "        RULES = {'e': (0, 4, 7),\n",
    "                'l': (3, 3, 3),\n",
    "                'o': (5, 2, 3),\n",
    "                'h': (7, 1, 1),\n",
    "                't': (8, 1, 1),\n",
    "                'c': (9, 1, 1),\n",
    "                'd': (10, 1, 1),}\n",
    "        FULL = 2012\n",
    "        costs = []\n",
    "        def merge(mask, j):\n",
    "            for c, b, k in RULES.values():\n",
    "                c1 = (mask >> c) & k\n",
    "                c2 = (j >> c) & k\n",
    "                if c1 + c2 > b: return -1\n",
    "                mask += c2 << c\n",
    "            return mask\n",
    "\n",
    "\n",
    "        def f(w, mask, c, cost):\n",
    "            if mask not in cost or cost[mask] > c:\n",
    "                cost[mask] = c\n",
    "            for i, j in enumerate(w):\n",
    "                if j not in RULES: continue\n",
    "                a, b, d = RULES[j]\n",
    "                if (mask >> a) & d < b:\n",
    "                    n_mask = (1 << a) + mask\n",
    "                    n_c = c + i*(len(w) - i - 1)\n",
    "                    f(w[:i] + w[i + 1:], n_mask, n_c, cost)\n",
    "        for i in words:\n",
    "            cost = {}\n",
    "            f(i, 0, 0, cost)\n",
    "            costs.append(cost)\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, mask):\n",
    "            if mask == FULL:\n",
    "                return 0\n",
    "            if i == len(words):\n",
    "                return math.inf\n",
    "            res = math.inf\n",
    "            for j, k in costs[i].items():\n",
    "                t = merge(mask, j)\n",
    "                if t >= 0:\n",
    "                    res = min(res, k + dfs(i + 1, t))\n",
    "            return res\n",
    "        r = dfs(0, 0)\n",
    "        return r if r != math.inf else -1\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
